package csdn;

import java.util.*;

class TreeNode {
    int val; // 数据域
    TreeNode left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
    TreeNode right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
    public TreeNode(int val){
        this.val=val;
    }
}
public class Csdn5 {
    //先序遍历
    public void preOrderTraversal1(TreeNode root){
        //如果该根结点为空则返回；
        if (root==null){
            return;
        }
        System.out.println(root.val);
        preOrderTraversal1(root.left);//开始递归该根的左孩子
        preOrderTraversal1(root.right);//开始递归该根的右孩子
    }
    //中序遍历
    public void inOrderTraversal1(TreeNode root){
        //如果该根结点为空则返回；
        if (root==null){
            return;
        }
        inOrderTraversal1(root.left);//开始递归该根的左孩子
        System.out.println(root.val);//访问结点
        inOrderTraversal1(root.right);//开始递归该根的右孩子
    }
    //后序遍历
    public void postOrderTraversal1(TreeNode root){
        //如果该根结点为空则返回；
        if (root==null){
            return;
        }
        postOrderTraversal1(root.left);//开始递归该根的左孩子
        postOrderTraversal1(root.right);//开始递归该根的右孩子
        System.out.println(root.val);//访问结点
    }
    public void preOrderTraversal(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();//创建一个栈
        if (root==null){
            return;
        }
        TreeNode cur=root;
        stack.push(cur);
        while (!stack.isEmpty()){
            TreeNode node=stack.pop();
            System.out.println(node.val);
            //先放右孩子，再放左孩子，因为栈是先进先出的特点
            if(node.right!=null){
                //右孩子不为空则将其放入栈里面
                stack.push(node.right);
            }
            if (node.left!=null){
                //左孩子不为空则将其放入栈里面
                stack.push(node.left);
            }
        }
    }
    public void inOrderTraversal(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if (root==null){//判断树是否为空
            return;
        }
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){//将左孩子放入其中
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.pop();
            System.out.println(cur.val);
            cur=cur.right;
        }
    }
    public void postOrderTraversal(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if (root==null){
            return;
        }
        TreeNode prev=null;
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.peek();
            //如果该结点的右孩子为空或者或者其右孩子已经被遍历
            if (cur.right==null||cur.right==prev){
                System.out.println(cur.val);
                stack.pop();
                prev=cur;
                cur = null;// 这个cur被打印了不能再次入栈
            }
            else {
                cur=cur.right;
            }
        }
    }
    public void levelOrderTraversal(TreeNode root) {
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {

            TreeNode top = queue.poll();
            System.out.print(top.val+" ");
            if(top.left != null) {
                queue.offer(top.left);
            }
            if(top.right!=null) {
                queue.offer(top.right);
            }
        }
    }
}
